<?php
	//------------------------------------------------------------------------------------------------------------------
	//Devolvemos una matriz con las fucniones de transición  
	function thompson($myRegex,$myAlfabeto){
				
		$tablaEstadosAFN = array();
		$numEstados = 0;		
		//Stack de automatas
		$stackAutomatas = new Stack();
		
		for ($i = 0; $i < strlen($myRegex); $i++){
			
			//--------------------------------------------------------------------------------------------------------------------------------------------			
			//Si es un simbolo del alfabeto creamos una transición de un estado a otro estado
			if ( in_array($myRegex[$i],$myAlfabeto) ){	
								
				//Numeracion estados
				$ne1 = $numEstados++;
				$ne2 = $numEstados++;
				
				//crear estados 				
				$estadoNuevo1 = new EstadoAFN($ne1,$myAlfabeto);
				$estadoNuevo2 = new EstadoAFN($ne2,$myAlfabeto);
				$estadoNuevo1->nuevaTransicion($myRegex[$i],$ne2);
				
				//crear nuevo automata
				$automata = new Automata();
				$automata->addEstado($estadoNuevo1,$ne1);
				$automata->addEstado($estadoNuevo2,$ne2);
				$automata->setEstadoInicial($ne1);
				$automata->setEstadoFinal($ne2);
				
				//Agregar automatata al Stack de automatas
				$stackAutomatas->push($automata);
				
				//Agregar estados a tabla de estados
				$tablaEstadosAFN[$ne1] = $automata->getEstado($ne1);
				$tablaEstadosAFN[$ne2] = $automata->getEstado($ne2);
								
				//Imprimir - con fin de pruebas
				//echo '<br/><br/>Stack automatas AGREGADO EL SIMBOLO "'.$myRegex[$i].'":<pre>';
				//print_r($stackAutomatas);
				//echo '</pre>';		
			}
			
			//--------------------------------------------------------------------------------------------------------------------------------------------
			//Si es Concatenación o Unión 
			else if ($myRegex[$i] == '.'){
								
				//(NO SE CREAN ESTADOS NUEVOS, SOLO SE CONCATENAN)
				//a. Sacamos del stack los utlimos dos automatas (o estados)
				$automata2 = $stackAutomatas->top();
				$stackAutomatas->pop();				
				$automata1 = $stackAutomatas->top();
				$stackAutomatas->pop();		
								
				//b. Crear nuevo automata
				$automata3 = new Automata;
				
				//c. Incluir en este automata todos los estados de los anteriores con todo y sus transiciones. 
				foreach($automata1->estados as $estado){
					$automata3->addEstado($estado,$estado->numero);	
				}
				foreach($automata2->estados as $estado){
					$automata3->addEstado($estado,$estado->numero);	
				}
				
				//d.Hacer transicion entre estado final de automata1 con etsado inicial de viejo automata 2
				$automata3->getEstado($automata1->getEstadoFinal())->nuevaTransicion('&',$automata3->getEstado($automata2->getEstadoInicial())->numero);				
				
				//e.Establecer estado inicial y estado final
				$automata3->setEstadoInicial( $automata3->getEstado($automata1->getEstadoInicial())->numero  );		
				$automata3->setEstadoFinal( $automata3->getEstado($automata2->getEstadoFinal())->numero );
				
				//f. Agregar nuevo automata al stack de automatas
				$stackAutomatas->push($automata3);
				
				//Imprimir - con fin de pruebas
				//echo '<br/><br/>Stack automatas CONCATENACION DE anteriores dos automatas:<pre>';
				//print_r($stackAutomatas);
				//echo '</pre>';						
			}			
			
			//--------------------------------------------------------------------------------------------------------------------------------------------
			//Si es Cerradura Kleene
			else if ($myRegex[$i] == '*'){
								
				//a. Sacamos del stack el ultimo automata
				$automata = $stackAutomatas->top();
				$stackAutomatas->pop();
				
				//b. Creamos dos estados nuevos				
				$ne1 = $numEstados++;
				$ne2 = $numEstados++;
				$estadoNuevo1 = new EstadoAFN($ne1,$myAlfabeto);
				$estadoNuevo2 = new EstadoAFN($ne2,$myAlfabeto);
				
				//c. Agregarmos estos dos neuvos etados a Automata
				$automata->addEstado($estadoNuevo1,$ne1);
				$automata->addEstado($estadoNuevo2,$ne2);

				
				//d. Establecemos el estado final e inicial de una vez.
				$estadoInicialViejo = $automata->getEstadoInicial();
				$estadoFinalViejo = $automata->getEstadoFinal();				
				$automata->setEstadoInicial($ne1);
				$automata->setEstadoFinal($ne2);
				
				//e. Realizamos transicion de etado nuevo 1 estado inicial de viejo
				$automata->getEstado($ne1)->nuevaTransicion('&',$estadoInicialViejo);				
				
				//f. Realizamos transicion de etado nuevo 1 estado nuevo 2			
				$automata->getEstado($ne1)->nuevaTransicion('&',$automata->getEstado($ne2)->numero);				
				
				//g. Realizamos transicion de etado final viejo y estado inicial viejo		
				$automata->getEstado($estadoFinalViejo)->nuevaTransicion('&',$estadoInicialViejo);				

				//h. Realizamos transicion de etado final viejo y estado nuevo 2		
				$automata->getEstado($estadoFinalViejo)->nuevaTransicion('&',$automata->getEstado($ne2)->numero);
				
				//i. Agregar nuevo automata al stack de automatas
				$stackAutomatas->push($automata);
				
				//j. Agregar estados nuevos a tabla de estados
				$tablaEstadosAFN[$ne1] = $automata->getEstado($ne1);
				$tablaEstadosAFN[$ne2] = $automata->getEstado($ne2);

								
				//Imprimir - con fin de pruebas
				//echo '<br/><br/>Stack automatas KLEIN de anteriores automata:<pre>';
				//print_r($stackAutomatas);
				//echo '</pre>';						

			}

			//--------------------------------------------------------------------------------------------------------------------------------------------
			//Si es cerradura Positiva
			else if ($myRegex[$i] == '+'){
								
				//a. Sacamos del stack el ultimo automata
				$automata = $stackAutomatas->top();
				$stackAutomatas->pop();
				
				//b. Creamos dos estados nuevos				
				$ne1 = $numEstados++;
				$ne2 = $numEstados++;
				$estadoNuevo1 = new EstadoAFN($ne1,$myAlfabeto);
				$estadoNuevo2 = new EstadoAFN($ne2,$myAlfabeto);
				
				//c. Agregarmos estos dos neuvos etados a Automata
				$automata->addEstado($estadoNuevo1,$ne1);
				$automata->addEstado($estadoNuevo2,$ne2);

				
				//d. Establecemos el estado final e inicial de una vez.
				$estadoInicialViejo = $automata->getEstadoInicial();
				$estadoFinalViejo = $automata->getEstadoFinal();				
				$automata->setEstadoInicial($ne1);
				$automata->setEstadoFinal($ne2);
				
				//e. Realizamos transicion de etado nuevo 1 estado inicial de viejo
				$automata->getEstado($ne1)->nuevaTransicion('&',$estadoInicialViejo);				
								
				//f. Realizamos transicion de etado final viejo y estado inicial viejo		
				$automata->getEstado($estadoFinalViejo)->nuevaTransicion('&',$estadoInicialViejo);				

				//g. Realizamos transicion de etado final viejo y estado nuevo 2		
				$automata->getEstado($estadoFinalViejo)->nuevaTransicion('&',$automata->getEstado($ne2)->numero);
				
				//h. Agregar nuevo automata al stack de automatas
				$stackAutomatas->push($automata);
				
				//i. Agregar estados nuevos a tabla de estados
				$tablaEstadosAFN[$ne1] = $automata->getEstado($ne1);
				$tablaEstadosAFN[$ne2] = $automata->getEstado($ne2);			
			}
			
			//--------------------------------------------------------------------------------------------------------------------------------------------			
			//Si es Concatenación o Unión 
			else if ( $myRegex[$i] == '|'){

				//a. Sacamos del stack los utlimos dos automatas (o estados)
				$automata2 = $stackAutomatas->top();
				$stackAutomatas->pop();				
				$automata1 = $stackAutomatas->top();
				$stackAutomatas->pop();		
								
				//b. Crear nuevo automata
				$automata3 = new Automata;

				//c. Incluir en este automata todos los estados de los anteriores con todo y sus transiciones. 
				foreach($automata1->estados as $estado){
					$automata3->addEstado($estado,$estado->numero);	
				}
				foreach($automata2->estados as $estado){
					$automata3->addEstado($estado,$estado->numero);	
				}
				
				//d. Creamos dos estados nuevos				
				$ne1 = $numEstados++;
				$ne2 = $numEstados++;
				$estadoNuevo1 = new EstadoAFN($ne1,$myAlfabeto);
				$estadoNuevo2 = new EstadoAFN($ne2,$myAlfabeto);
				
				//e. Agregarmos estos dos neuvos etados a Automata
				$automata3->addEstado($estadoNuevo1,$ne1);
				$automata3->addEstado($estadoNuevo2,$ne2);

				//f. Establecemos el estado final e inicial de una vez.
				$estadoInicialViejo1 = $automata1->getEstadoInicial();
				$estadoFinalViejo1 = $automata1->getEstadoFinal();
				$estadoInicialViejo2 = $automata2->getEstadoInicial();
				$estadoFinalViejo2 = $automata2->getEstadoFinal();
				$automata3->setEstadoInicial($ne1);
				$automata3->setEstadoFinal($ne2);
								
				//g. Realizamos transicion de etado nuevo 1 estado inicial de viejo
				$automata3->getEstado($ne1)->nuevaTransicion('&',$estadoInicialViejo1);				
				$automata3->getEstado($ne1)->nuevaTransicion('&',$estadoInicialViejo2);				

				//h. Realizamos transicion de etado final viejo y estado nuevo 2		
				$automata3->getEstado($estadoFinalViejo1)->nuevaTransicion('&',$automata3->getEstado($ne2)->numero);
				$automata3->getEstado($estadoFinalViejo2)->nuevaTransicion('&',$automata3->getEstado($ne2)->numero);

				//i. Agregar nuevo automata al stack de automatas
				$stackAutomatas->push($automata3);
				
				//j. Agregar estados nuevos a tabla de estados
				$tablaEstadosAFN[$ne1] = $automata3->getEstado($ne1);
				$tablaEstadosAFN[$ne2] = $automata3->getEstado($ne2);

								
				//Imprimir - con fin de pruebas
				//echo '<br/><br/>Stack automatas UNION de dos automatas:<pre>';
				//print_r($stackAutomatas);
				//echo '</pre>';						
				
			}
		}
		$automataFinal = $stackAutomatas->top();			
		$stackAutomatas->pop();
		$tablaEstadosAFN[$automataFinal->getEstadoInicial()]->inicial = 1;
		$tablaEstadosAFN[$automataFinal->getEstadoFinal()]->aceptacion = 1;
		
		//Imprimir - con fin de pruebas
		//echo '<br/><br/>Stack automatas KLEIN de anteriores automata:<pre>';
		//print_r($tablaEstadosAFN);
		//echo '</pre>';			
		
		//--------------------------------------------------------------------------------------------------------------------------------------------			
		//Impresion
		
		echo '<h2>Algoritmo de Thompson</h2>';

		//Imprimir - tabla de estados
		
		echo'Tabla de estados y transiciones:</br><table border="1" cellalign="center" cellpadding="10">';
		echo'<tr><td width="25%">Estado</td>';
		
		foreach($myAlfabeto as $simbolo)
			echo '<td>'.$simbolo.'</td>';	
		echo '<td> &#x03F5; </td> </tr>';
		
		foreach($tablaEstadosAFN as $estado){
			echo '<tr><td>S'.$estado->numero.'</td>';
			foreach($estado->transiciones as $transicion){
				echo '<td>';
				if ($transicion!=NULL){
					$comas=0; 
					foreach($transicion as $subtransicion){
						if ($comas==0)
							echo ' S'.$subtransicion;
						else
							echo ', S'.$subtransicion;						
						$comas++; 
					}
				}
				echo '</td>';
			}		
			echo '</tr>';
				
		}	
				
		echo '</table><ul>';
		
		$enArchivo = '==== Algorimo de Thompson ===='.PHP_EOL.PHP_EOL.'Estados = {';
		//Imprimir Estados
		echo '<li>Estados = {';
		$cont=0;		
		foreach ($tablaEstadosAFN as $estado) {
	  		if ($cont==0){
	  			echo $estado->numero;
				$enArchivo = $enArchivo.$estado->numero;
			}
	  		else{
	  			echo ', '.$estado->numero;	
				$enArchivo = $enArchivo.', '.$estado->numero;
	  		}
	  		$cont++;  		
		}
		echo '}';		
		$enArchivo = $enArchivo.'}'.PHP_EOL.PHP_EOL;
		
		//Impimir alfabeto
		$enArchivo = $enArchivo.'Simbolos = {';
		echo '</li><li>Simbolos = {';
		$cont=0;
		foreach ($myAlfabeto as $simbolo) {
	  		if ($cont==0){
	  			echo $simbolo;
	  			$enArchivo = $enArchivo.$simbolo;
	  		}
	  		else{
	  			echo ', '.$simbolo;	  	
	  			$enArchivo = $enArchivo.', '.$simbolo;
	  		}
	  		$cont++;  			  				
		}
		echo '}';		
		$enArchivo = $enArchivo.'}'.PHP_EOL.PHP_EOL;
				
		
		//Imprimir estado inicial
		$enArchivo = $enArchivo.'Inicio = {';		
		echo '</li><li>Inicio = {';
		echo $automataFinal->getEstadoInicial();	
	  	$enArchivo = $enArchivo.$automataFinal->getEstadoInicial();
		echo '}';		
		$enArchivo = $enArchivo.'}'.PHP_EOL.PHP_EOL;

		//Imprimir estado de aceptación
		$enArchivo = $enArchivo.'Aceptacion = {';				
		echo '</li><li>Aceptacion = {';
		echo $automataFinal->getEstadoFinal();
	  	$enArchivo = $enArchivo.$automataFinal->getEstadoFinal();			
		echo '}';					
		$enArchivo = $enArchivo.'}'.PHP_EOL.PHP_EOL;
		
		//Imprimir transiciones
		$enArchivo = $enArchivo.'Transiciones = {';						
		echo '</li><li>Transiciones = ';
		
		$cont=0;
		foreach($tablaEstadosAFN as $estado){
		
			foreach($estado->transiciones as $sim=>$transicion){
				if ($transicion!=NULL){
					foreach($transicion as $subtransicion){
						if ($sim=="&"){$sim1 = '&#x03F5;'; $sim2 = 'E';} else {$sim1 = $sim; $sim2 = $sim;}
						if ($cont==0){
							echo '('.$estado->numero.', '.$sim1.', '.$subtransicion.')';
							  $enArchivo = $enArchivo.'('.$estado->numero.', '.$sim2.', '.$subtransicion.')';			
						}
						else{
							echo ' - ('.$estado->numero.', '.$sim1.', '.$subtransicion.')';
	  						$enArchivo = $enArchivo.' - ('.$estado->numero.', '.$sim2.', '.$subtransicion.')';			
	  					}
	  					$cont++;  			  				
					}
				}
			}		
		}	
					
		echo '</li></ul>';				
		$enArchivo = $enArchivo.'}'.PHP_EOL.PHP_EOL;
		
		//Archivos
		unlink('archivoThompson.txt');
		if($fp=fopen('archivoThompson.txt','ab')){
		flock($fp, LOCK_EX);
		//write to the file
		fwrite($fp,$enArchivo);
		flock($fp,LOCK_UN);
		fclose($fp);
		echo "La informacion ha sido guardada en un archivo de texto <a href='archivoThompson.txt'>aca.</a>";
		}else{
		echo "Error al escribir el archivo";
		}		
	
	return $tablaEstadosAFN;

	}
	
	
?>